CF700B Connecting Universities

巧妙的思维题

题解：

直接硬配求贡献的方法显然是难以实现的，所以我们需要转换思路：

考虑计算每条边的贡献，边的贡献和就是我们的答案

举个例子，看下面这张图：

红边将大学分成了左右两个点集，在所有的配对方案中，从左右点集各选一个点配对肯定是最优先考虑的

为什么呢？因为同一集合中选点，距离都是固定的，但从不同集合选点，还能够额外加上一条红边的价值

也就是说贪心思路就是要最大化左右两端配对的方案数

如果设左点集为$A$，右点集为$B$，显然的，连接它们的边的价值就是$\min(|A|,|B|)$

因为$|A|+|B|=2*k$，所以只需要知道每条边一侧的大学数

又因为这是一棵树，从下往上统计一个点子树内的大学数可以了

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=2e5+5;
int en,n,m,h[N],a[N];
long long ans;

struct edge{
    int n,v;
}e[N<<1];

void add(int x,int y){
    e[++en]=(edge){h[x],y};
    h[x]=en;
}

void dfs(int x,int fa){
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(y==fa) continue;
        dfs(y,x);
        a[x]+=a[y];
    }
    ans+=min(a[x],m-a[x]);
}

signed main(){
    read(n);read(m);m<<=1;
    for(int i=1,x;i<=m;i++)
        a[read(x)]=1;
    for(int i=1,x,y;i<n;i++){
        read(x);read(y);
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    write(ans);
}